/**
 * ContainsBinaryTree.java created by zhangzhidong 
 * at 上午9:47:26 2016年4月25日
 */
package algorithm.CIG.binarytree;

import algorithm.CIG.base.TreeNode;

/**
 * @author zhangzhidong
 *
 */
public class ContainsBinaryTree extends VisualTree {
	
	public static void main (String args[]){
		TreeNode t1 = generateTree();
		TreeNode t2 = generateSubTree();
		printTree(t1);
		sepratorLine();
		printTree(t2);
		System.out.println(contains(t1, t2));
	}
	public static boolean contains(TreeNode t1,TreeNode t2){
		return check(t1,t2)||check(t1.left,t2)||check(t1.right,t2);
	}
	//判断,以t1为根的子树是不是包含t2为根的树,t1和t2的值需一致
	public static boolean check(TreeNode t1,TreeNode t2){
		if(t2==null) return true;
		if(t1==null || t2.val!=t1.val)return false;
		return check(t1.left,t2.left) && check(t1.right,t2.right);
	}
	
	public static TreeNode generateTree(){
		TreeNode t1 = new TreeNode(1);
		t1.left = new TreeNode(2);
		t1.right = new TreeNode(3);
		t1.left.left = new TreeNode(4);
		t1.left.right = new TreeNode(5);
		t1.right.left = new TreeNode(6);
		t1.right.right = new TreeNode(7);
		t1.left.left.left = new TreeNode(8);
		t1.left.left.right = new TreeNode(9);
		t1.left.right.left = new TreeNode(10);
		return t1;
	}
	public static TreeNode generateSubTree(){
		TreeNode t2 = new TreeNode(2);
		t2.left = new TreeNode(4);
		t2.left.left = new TreeNode(8);
		t2.right = new TreeNode(5);
		return t2;
	}
}
